package listbyorder.access301_400.test378;

public class Solution1 {

    // 二分查找算法
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length - 1;
        int left = matrix[0][0];
        int right = matrix[n][n];
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = getMidCount(matrix, mid, n);  // 寻找当前的mid在数组中插入的位置
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // 获取当前数组中的最小的中间值
    private int getMidCount(int[][] matrix, int mid, int n) {
        int count = 0;
        int x = 0, y = n;
        while (x <= n && y >= 0) {
            if (matrix[y][x] <= mid) {
                count += y + 1;
                x++;
            } else {
                y--;
            }
        }
        return count;
    }
}
